package day20;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。
 *
 * 请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
 *
 * mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
 * maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。
 * 返回数组 answer 。
 *
 *
 *
 * 示例 1 ：
 *
 *
 *
 * 输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
 * 输出：[[2,2],[4,6],[15,-1]]
 * 解释：按下面的描述找出并返回查询的答案：
 * - 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
 * - 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
 * - 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。
 * 示例 2 ：
 *
 *
 *
 * 输入：root = [4,null,9], queries = [3]
 * 输出：[[-1,4]]
 * 解释：树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution2 {
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        List<List<Integer>> ansList  = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        middlePlic(root,list);
        for (Integer query : queries) {
            ansList.add(Find(list,query));
        }
        return ansList;
    }
    public void middlePlic(TreeNode root,List list){
        if(root == null){
            return;
        }
        middlePlic(root.left,list);
        list.add(root.val);
        middlePlic(root.right,list);
    }
    public List<Integer> Find(List<Integer> list,int num){
        int left = 0,right = list.size()-1;
        List<Integer> doList = new ArrayList<>();
        if(num>list.get(right)){
            doList.add(list.get(right));
            doList.add(-1);
            return doList;
        }
        if(num<list.get(left)){
            doList.add(-1);
            doList.add(list.get(left));
            return doList;
        }
        while (left<right){
            int mid = (right-left)/2 + left;
            if(num>list.get(mid)){
                left=mid+1;
            }else if(num<list.get(mid)){
                right = mid;
            }else if(num==list.get(mid)){
                doList.add(num);
                doList.add(num);
                return doList;
            }
        }

        doList.add(list.get(left));
        return doList;
    }
}
